#include <vector>
#include <string>
#include <map>
#include <algorithm>

using namespace std;

// 核心思路：利用 “字母异位词排序后为相同字符串” 的特性，通过 “生成模板 + map 分组” 实现归类，具体步骤如下：

// 1.明确字母异位词特征：这类单词包含的字母及每个字母的个数完全相同，仅排列顺序不同，
// 因此它们排序后会得到同一个 “标准模板字符串”。

// 2.生成每个单词的模板字符串：遍历输入的字符串列表 strs，对每个单词执行三步操作 —— 先拆分成单个字符存入 vector<char>，
// 再对该字符 vector 进行排序，最后将排序后的字符重新组合成字符串，这个字符串就是当前单词的 “模板”。

// 3.用 map 进行分组存储：定义 map<string, vector<string>> 类型的容器，以步骤 2 生成的 “模板字符串” 作为 key，
// 以对应的字母异位词列表作为 value。遍历每个单词时，将其添加到 map 中对应模板 key 的 vector 里，
// 实现自动分组（相同模板的单词会被归为一组）。

// 4.收集结果并返回：遍历整个 map，将 map 中每个 key 对应的 vector（即每一组字母异位词）依次存入要返回的
//  vector<vector<string>> 类型容器 retarr 中，最终返回 retarr 即可。


class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> retarr;
        map<string,vector<string>> m;

        if (strs.empty()) 
            return retarr;

        for(auto& e:strs)
        {
            vector<char> tmp;
            for(int i =0;i<e.size();i++)
            {
                tmp.push_back(e[i]);
            }

            std::sort(tmp.begin(),tmp.end());
            string tmp_s;
            for(auto& ch:tmp)
            {
                tmp_s += ch;
            }

            m[tmp_s].push_back(e);
        }


        // 遍历map
        map<string, vector<string>>::iterator it = m.begin();
        while (it != m.end())
        {
            // 直接将map中当前key对应的vector加入结果（避免retarr[index]越界）
            retarr.push_back(it->second); 
            it++; 
        }

        // // 遍历map，收集所有分组
        // for (auto& pair : m) { // 用范围for更简洁
        //     retarr.push_back(pair.second); // 直接将分组插入结果
        // }

        return retarr;
    }
};